//p5250

#include <iostream>
#include <set>

int main()
{
    int n; std::cin >> n;
    std::set<int> s;
    for (int i = 0; i < n; i ++)
    {
        int sig, num; std::cin >> sig >> num;

        if (sig == 1) //插入
        {
            if (s.count(num)) //已经存在啦 
                std::cout << "Already Exist" << std::endl;
            else s.insert(num);
        }
        else if (sig == 2) //查询 - 修改为else if结构
        {
            if (s.empty()) std::cout << "Empty" << std::endl; //空的情况
            else //非空的情况
            {
                auto itr = s.lower_bound(num); //每一次查询均要重新创建一个迭代器
                
                if (itr != s.end() && *itr == num) //安全检查
                {
                    std::cout << num << std::endl;
                    s.erase(itr); //直接使用迭代器删除更高效
                }
                else //不相等
                {
                    if (itr == s.end()) //后指针打到结尾
                    {
                        --itr; //先移动再访问
                        std::cout << *itr << std::endl;
                        s.erase(itr);
                    }
                    else if (itr == s.begin()) //避免对begin()进行自减操作
                    {
                        std::cout << *itr << std::endl;
                        s.erase(itr);
                    }
                    else //不头不尾
                    {
                        auto itr2 = itr;
                        --itr2; //先保存当前迭代器再创建前一个迭代器
                        int front_num = *itr2, back_num = *itr;
                        if ((num - front_num) <= (back_num - num))
                        {
                            std::cout << *itr2 << std::endl;
                            s.erase(itr2);
                        }
                        if ((num - front_num) > (back_num - num))
                        {
                            std::cout << *itr << std::endl;
                            s.erase(itr);
                        }
                    }
                }
            }
        }
    }
    return 0;
}